package no11;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/23 11:11
 * 旋转数组的最小数字
 * https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 */
public class Solution {

    public int minArray(int[] numbers) {
        // 使用二分查找，时间复杂度O(log n)
        int left = 0;
        int right = numbers.length - 1;
        // 可以发现 一般情况下 旋转数组 分为了左右两个部分
        // 左排序数组的最右侧元素 一定大于 右排序数组的所有元素
        // 二分的核心就是判断 mid 处于哪个排序数组中，并缩小检索范围
        int mid = 0; // 返回的结果 同时也是二分的迭代条件
        while(left < right){
            mid = left - ((left - right) / 2);
            if(numbers[mid] < numbers[right]){
                // mid 处于右排序数组
                right = mid;
            }else if(numbers[mid] > numbers[right]){
                // mid 处于左排序数组
                left = mid + 1;
            }else{
                // 相同的情况下无法判断，只需要进行缩小范围
                right--;
            }
        }
        return numbers[left];
    }
}
